#define _CRT_SECURE_NO_WARNINGS 2
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

struct TreeNode
{
public:
	TreeNode(int val)
		:val_(val)
		,left_(nullptr)
		,right_(nullptr)
	{}

public:
	int val_;
	TreeNode* left_;
	TreeNode* right_;

	
};

class BST
{
public:
	BST(TreeNode* root=nullptr)
		:root_(root)
	{}

	bool _insert_recursion(TreeNode*& root,const int& val)
	{
		if (root == nullptr)
		{
			root = new TreeNode(val);
			return true;
		}
		if (root->val_ > val)
			return _insert_recursion(root->left_, val);
		else if (root->val_ < val)
			return	_insert_recursion(root->right_, val);
		else
			return false;
	}

	bool insert_recursion(int val)
	{
		return _insert_recursion(root_, val);
	}

	bool Insert(int val)
	{
		if (root_ == nullptr)
		{
			root_ = new TreeNode(val);
			return true;
		}

		TreeNode* cur = root_, * parent = root_;
		while (cur)
		{
			if (cur->val_ == val)
				return false;
			else if (cur->val_ < val)
			{
				parent = cur;
				cur = cur->right_;
			}
			else
			{
				parent = cur;
				cur = cur->left_;
			}
		}

		if(parent->val_>val)
			parent->left_= new TreeNode(val);
		else
			parent->right_ = new TreeNode(val);

		return true;
	}

	bool _erase_recursion(TreeNode*& root, const int& val)
	{
		if (root == nullptr)
			return false;
		if (root->val_ > val)
			return _erase_recursion(root->left_, val);
		else if (root->val_ < val)
			return _erase_recursion(root->right_, val);
		else
		{
			TreeNode* tmp = root;
			//left is nullptr
			if (root->left_ == nullptr)
				root = root->right_;
			else if (root->right_ == nullptr)
				root = root->left_;
			else
			{
				TreeNode* left_max = root->left_, * parent = root;
				while (left_max->right_)
				{
					parent = left_max;
					left_max = left_max->right_;
				}
				swap(root->val_, left_max->val_);
				tmp = left_max;
				/*if (parent->left_ == left_max)
					parent->left_ = nullptr;
				else
					parent->right_ = nullptr;*/
				return _erase_recursion(root->left_, val);
			}
			delete tmp;
			tmp = nullptr;
		}

		return true;
	}

	bool erase_recursion(const int& val)
	{
		return _erase_recursion(root_, val);
	}

	bool Erase(int val)
	{
		TreeNode* cur = root_, * parent = root_;
		while (cur)
		{
			if (cur->val_ < val)
			{
				parent = cur;
				cur = cur->right_;
			}
			else if (cur->val_ > val)
			{
				parent = cur;
				cur = cur->left_;
			}
			else
			{
				if (cur->left_ == nullptr)
				{
					if (root_ == cur)
						root_ = cur->right_;
					else
					{
						if (parent->left_ == cur)
							parent->left_ = cur->right_;
						else
							parent->right_ = cur->right_;
					}
				}
				else if (cur->right_ == nullptr)
				{
					if (root_ == cur)
						root_ = cur->left_;
					else
					{
						if (parent->left_ == cur)
							parent->left_ = cur->left_;
						else
							parent->right_ = cur->left_;
					}
				}
				else
				{
					parent = cur;
					TreeNode* left_max = cur;
					while (left_max->right_)
					{
						cur = left_max;
						left_max = left_max->right_;
					}
					swap(parent->val_, left_max->val_);
					if (cur->left_ == left_max)
						cur->left_ = nullptr;
					else
						cur->right_ = nullptr;
					cur = left_max;
				}
				delete cur;
				cur = nullptr;
				return true;
				//TreeNode* tmp = root_;
				////cur_left is nullptr
				//if (cur->left_ == nullptr)
				//{
				//	if (parent->left_ == cur)
				//		parent->left_ = cur->right_;
				//	else
				//		parent->right_ = cur->right_;
				//	if (root_ == cur)
				//		root_ = cur->right_;
				//	tmp = cur;

				//}
				////cur_right is nullptr
				//else if (cur->right_ == nullptr)
				//{
				//	if (parent->left_ == cur)
				//		parent->left_ = cur->left_;
				//	else
				//		parent->right_ = cur->left_;
				//	tmp = cur;
				//}
				////cur_left && cur_right is existed;
				//else
				//{

				//	TreeNode* left_max = cur;
				//	parent = cur;
				//	while (left_max->right_)
				//	{
				//		cur = left_max;
				//		left_max = left_max->right_;
				//	}
				//	swap(left_max->val_, parent->val_);
				//	tmp = left_max;
				//	cur->right_ = nullptr;
				//}
				//delete tmp;
				//tmp = nullptr;
				//return true;
			}
		}
		
		return false;
	}

	void InOrder(TreeNode* root)
	{
		if (root == nullptr)
			return;
		InOrder(root->left_);
		cout << root->val_ << " ";
		InOrder(root->right_);
	}

	void Print()
	{
		InOrder(root_);
		cout << endl;
	}

	~BST()
	{}
protected:
	TreeNode* root_;
};

void Test()
{
	BST root;
	root.insert_recursion(4);
	root.insert_recursion(5);
	root.insert_recursion(0);
	root.insert_recursion(-1);
	root.Insert(90);
	root.insert_recursion(-90);
	root.insert_recursion(8);
	root.Print();
	root.erase_recursion(4);
	root. erase_recursion(5);
	root.Print();
	root.Print();
	root. erase_recursion(-1);
	root. erase_recursion(90);
	root.Print();

	root. erase_recursion(-90);
	root. erase_recursion(8);
	root.Print();

	root. erase_recursion(0);
	root.Print();
	root. erase_recursion(5);


}

void Test2(int& a)
{

}

int main()
{
	int a = 2;
	Test2(a);
	return 0;
}